maze = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
    [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]

def print_path(Close):
    path = []
    tmp = Close[-1]
    while tmp[3] != -1:
        path.append(Close[tmp[3]][0:2])
        tmp = Close[tmp[3]]
    path.reverse()
    print(f'BFS 得最短路径如下: ')
    for i in path:
        print(f'{i} → ', end='')
    print(f'{(Close[-1][0], Close[-1][1])}')
    print(f'长度为 {len(path)}, 总试探步数 {len(Close) - 1}')


def BFS(x0, y0, x1, y1):
    visited = []
    Open = [(x0, y0, 0, -1)]  # 横、纵坐标, 当前节点在path中的下标，父节点在path中的下标
    Close = []
    while Open:
        cur = Open.pop(0)
        Close.append(cur)
        visited.append((cur[0], cur[1]))
        if (cur[0], cur[1]) == (x1, y1):
            print_path(Close)
            return
        for dir in dirs:
            tmp = (cur[0] + dir[0], cur[1] + dir[1], len(Close), cur[2])
            if 0 < tmp[0] < 9 and 0 < tmp[1] < 9 and (tmp[0], tmp[1]) not in visited and maze[tmp[0]][tmp[1]] == 0:
                visited.append((tmp[0], tmp[1]))
                Open.append(tmp)


BFS(1, 1, 8, 8)
